#define _CRT_SECURE_NO_WARNINGS
#define MAXSIZE 20
typedef int KeyType;
typedef int InfoType;
typedef struct {
	KeyType key;
	InfoType otherinfo;
}ElemType;
typedef struct {
	ElemType r[MAXSIZE];
	int length;
}SqList;
void InsertSort(SqList& L)
{
	int i,j;
	for (i = 2; i <= L.length; i++)
	{
		if (L.r[i].key< L.r[i - 1].key)
		{
			L.r[0] = L.r[i];
			L.r[i] = L.r[i - 1];
			for (j = i - 2; L.r[0].key < L.r[j].key; j--)
				L.r[j + 1] = L.r[j];
			L.r[j + 1] = L.r[0];
		}
	}
}
void BInsertSort(SqList& L)
{
	int i, j;
	int low, high, mid;
	for (i = 2; i <= L.length; i++)
	{
		L.r[0] = L.r[i];
		low = 1; high = i - 1;
		while (low < high)
		{
			mid = (low + high) / 2;
			if (L.r[0].key < L.r[mid].key) high = mid - 1;
			else low = mid + 1;
		}
		for (j = i - 1; j >= high + 1; j--) L.r[j + 1] = L.r[j];
		L.r[high + 1] = L.r[0];
	}
}
void Shelllnsert(SqList& L, int dk)
{
	int i, j;
	for (i = dk + 1; i <= L.length; i++)
	{
		if (L.r[i].key < L.r[i -dk].key)
		{
			L.r[0] = L.r[i];
			for (j = i - dk; j > 0 && L.r[0].key < L.r[j].key; j -= dk)
			{
				L.r[j + dk] = L.r[j];
			}
			L.r[j + dk] = L.r[0];

		}
	}
}
void ShellSort(SqList& L, int dlta[], int t)
{
	int k;
	for (k = 0; k < t; ++k)
	{
		Shelllnsert(L, dlta[k]);
	}
}
int Partition(SqList& L, int low, int high)
{
	int pivotkey;
	L.r[0] = L.r[low];
	pivotkey = L.r[low].key;
	while (low < high)
	{
		while (low < high && L.r[high].key >= pivotkey) --high;
		L.r[low] = L.r[high];
		while (low < high && L.r[low].key <= pivotkey) ++low;
		L.r[high] = L.r[low];

	}
	L.r[low] = L.r[0];
	return low;
}
void QSort(SqList& L, int low, int high)
{
	int pivotloc;
	if (low < high)
	{
		pivotloc = Partition(L, low, high);
		QSort(L, low, pivotloc - 1);
		QSort(L, pivotloc + 1, high);

	}
		
}
void QuickSort(SqList& L)
{
	QSort(L, 1, L.length);
}
void InsertSort(SqList* L)
{
	int r;
	int i = 1, j;
	while (i < L->length)
	{
		if (L->list[i] < L->list[i - 1])
		{
			r = L->list[i];
			L->list[i] = L->list[i - 1];
			for (j = i - 2; r < L->list[j]; j--)
			{
				L->list[j + 1] = L->list[j];
				if (j == -1)break;
			}
			L->list[j + 1] = r;

		}
		j = 0;
		while (j < L->length)
		{
			printf("%d ", L->list[j]);
			j++;
		}
		printf("\n");
		i++;
	}
}
